#ifndef TEMPLATE_HEAP_H
#define TEMPLATE_HEAP_H

#include <iostream>
#include <algorithm>
#include <cassert>

template <class T, unsigned size>
class TemplateHeap
{
public:
	TemplateHeap()
		:	elements(0),
			data(new T[size])
	{
	}

	virtual ~TemplateHeap()
	{
		delete[] data;
	}

	T top() const
	{
		assert(elements > 0);
		return data[0];
	}

	void push(T element)
	{
		assert(elements < size);
		unsigned idx = elements;
		data[elements++] = element;

		while(idx != 0)
		{
			unsigned pidx = parent_index(idx);

			if(data[pidx] < element)
				std::swap(data[idx], data[pidx]);
			else
				break;
			idx = pidx;
		}
	}

	void pop()
	{
        assert(elements > 0);
            
        data[0] = data[--elements];
        unsigned idx = 0;
            
        do 
		{
            unsigned childs = children(idx);
            if (childs == 0) 
				break;

            unsigned max_idx = left_index(idx);
            if (childs == 2) 
			{
                if (data[max_idx] < data[max_idx + 1]) 
                    max_idx++;
            }
            if (data[idx] < data[max_idx]) 
			{
                std::swap(data[idx], data[max_idx]);
                idx = max_idx;
            }
            else 
				break;
                
        } 
		while (true);
	}

	void print()
	{
		if(elements > 0)
			printIndex(0);
	}

private:
	void printIndex(unsigned index)
	{
		std::cout << data[index];
		if(index != 0)
			std::cout << " parent: " << data[parent_index(index)];
		std::cout << std::endl;

		unsigned childs = children(index);
		if(childs >= 1)
			printIndex(left_index(index));
		if(childs >= 2)
			printIndex(right_index(index));
	}

	unsigned elements;
    T *data;

    unsigned left_index(unsigned idx) const 
	{ 
		return 2 * idx + 1; 
	}

    unsigned right_index(unsigned idx) const 
	{ 
		return 2 * idx + 2; 
	}

    unsigned parent_index(unsigned idx) const 
	{ 
		return (idx - 1) / 2; 
	}

    unsigned children(unsigned idx) const 
	{
        if (elements <= left_index(idx)) 
			return 0;
        if (elements > right_index(idx)) 
			return 2;
        return 1;
    }
};
#endif